// 416. 分割等和子集

function canPartition(nums: number[]): boolean {
  let sum = 0;
  for (let num of nums) {
    sum += num;
  }
  if (sum % 2 === 1) return false;
  const target = sum / 2;

  const dp: number[] = new Array(target + 1).fill(0);

  for (let i = 0; i < nums.length; i++) {
    for (let j = target; j >= nums[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
    }
  }

  console.log(dp);
  return dp[target] === target;
}

const nums17 = [1, 5, 11, 5];

console.log(canPartition(nums17));
// copy 及其nb的思路
/*
       重温0-1背包问题:(空间优化/状态压缩)
       此问题相当于求是否能凑成target=sum/2的子集
       抽象成在一堆重量为nums[i],价值也为nums[i]的物品中,能否恰好装满容量为target的背包
       dp五部曲(一维数组方案):
       1.状态定义:dp[j]为容量为j的背包最多能装的物品价值是多少?
           为什么要最多?因为要逼近背包容量极限,因此当能凑出target的情形,dp[j]必定为target
       2.状态转移:考虑到nums[i],根据背包容量j与nums[i]大小分为两种情形:
           2.1 j<nums[i]说明把背包腾空也装不下nums[i],dp[j](新)=dp[j](旧:上一轮考虑nums[0]~nums[i-1]的)
               意思就是j容量的背包最多能装的价值继承考虑nums[0]~nums[i-1]的物品
           2.2 j>=nums[i]说明把可以装下nums[i],那么dp[j]=max(dp[j](旧),dp[j-nums[i]]+nums[i])
               容量够装nums[i],在装与不装nums[i]中选一个大的值,不装nums[i]的最大价值就是dp[j](旧)
               装了nums[i]的最大价值就是dp[j-nums[i]]+nums[i]==>
               考虑nums[0]~nums[i-1]腾出足够空间装下nums[i](就是装一点,后面还要装nums[i]呢)的价值+nums[i]本身
               两者之中取大的就是新的dp[j](新)
       3.初始化边界:由于转移需要用到上一轮左边的值,因此要初始化最左边的即可,dp[0]=0
       4.遍历顺序:这里有讲究了~~~首先遍历物品正反顺序没讲究,但是必须先遍历物品后遍历背包容量
           而且遍历容量的顺序必须是倒序,因为倒序才是利用上一轮旧的dp[j]进行转移,正序用的是本轮的
           既然是倒序遍历容量,那么先遍历物品后遍历背包容量原因显而易见了
           若先遍历背包容量,dp[target]只装了一个最大的nums[i],就装了一个物品!!!显然不合题意
       5.返回坐标:返回dp[target]==target(考虑所有nums[i],最大容量为target的背包能否凑出target的价值)
       */
